\documentclass[a4paper,10pt]{article}

\usepackage{graphicx}
\usepackage[cm]{fullpage}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{hyperref}

% commands for setting up the page
\parindent0mm
\pagestyle{empty}

\sloppy

% environment for "exercise"
\newcounter{exc}
\setcounter{exc}{4}
\newenvironment{exercise}[1]%
{\refstepcounter{exc}\textbf{Exercise \arabic{exc}} \emph{#1}\\}
{

\hrulefill\medskip}%

\newenvironment{solution}
{
\medskip

\textbf{Solution}

}
{ \medskip }

\renewcommand{\labelenumi}{(\alph{enumi})}

\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\vc}[1]{\boldsymbol{#1}}
\newcommand{\LP}{\mathrm{LP}}
\newcommand{\LD}{\mathrm{LD}}
\newcommand{\conv}{\mathrm{conv}}

\begin{document}

%% Header
\begin{center}
  {\large \bf Exercises for\\
    Mathematical Programming\\
    186.835 VU 3.0 - SS 14}\\
  \bigskip
  Last update: \today
\end{center}

\hrulefill\medskip

Group members:
\begin{enumerate}
\item Christian Hafner, 0925172, chafner@cg.tuwien.ac.at
\item Klemens Jahrmann, 0826080, klemens.jahrmann@tuwien.ac.at
\item Kevin Streicher, 1025890, e1025890@student.tuwien.ac.at
\end{enumerate}

\hrulefill\medskip

\begin{exercise}{Lagrangian Relaxation for Uncapacitated Facility Location}\label{ex:lag-ufl}
We are given the formulation on slide 54 for the Uncapacitated Facility Location Problem. In the lecture we dualized the demand constraints. Your task is to dualize the linking constraints $x_{ij} \le y_j,~ \forall i \in M,~ \forall j \in N$, in the usual Lagrangian way. How strong is the best Lagrangian dual bound achievable by this relaxation compared to the optimal LP relaxation value of the original formulation? How easy is it to solve the Lagrangian subproblem(s)?

\begin{solution}
	\input{ex5.tex}
	
\end{solution}

\end{exercise}

\begin{exercise}{Lagrangian Relaxation for Knapsack Problems}\label{ex:lag-kp}
Consider the 0-1 knapsack problem
\begin{align}
 z = \max \quad 10 y_1 + 4 y_2 + 14 y_3 & \\
 \label{eq:lag-kp} 3 y_1 + y_2 + 4 y_3 & \le 4 \\
 y_1,y_2,y_3 & \in \{0,1\}
\end{align}
Dualize the knapsack constraint~\eqref{eq:lag-kp} in the usual Lagrangian way. What is the optimal value of the Lagrange multiplier $u$ and the value of the Lagrangian dual $w_{LD}$?
Run the subgradient algorithm using the step size method (rule (2) on slide 68) with $u^0 = 0,~ \mu_0 = 1,~ \rho = 0.5$. Does the subgradient algorithm converge to $w_{LD}$?

\begin{solution}
	\input{ex6.tex}
	
\end{solution}

\end{exercise}


\begin{exercise}{Lagrangian Decomposition}\label{ex:lag-decomp}
Consider the problem
\begin{align}
 z = \max \quad \vc{c}' \vc{x} & \\
 \vc{A}^1 \vc{x} & \le \vc{b}^1 \\
 \vc{A}^2 \vc{x} & \le \vc{b}^2 \\
 \vc{x} & \in \Z^n_+
\end{align}
with the reformulation
\begin{align}
 z = \max \quad \alpha \vc{c}' \vc{x} + (1 - \alpha) \vc{c}' \vc{y} & \\
 \vc{A}^1 \vc{x} & \le \vc{b}^1 \\
 \vc{A}^2 \vc{y} & \le \vc{b}^2 \\
 \label{eq:lag-decomp} \vc{x} - \vc{y} & = \vc{0} \\
 \vc{x},\vc{y} & \in \Z^n_+
\end{align}
for $0 < \alpha < 1$. Consider the Lagrangian dual of this formulation in which the $n$ constraints~\eqref{eq:lag-decomp} are dualized. Discuss the strength of this Lagrangian dual compared to the optimal LP relaxation value of the original formulation!

\begin{solution}
	\input{ex7.tex}
	
\end{solution}

\end{exercise}


\begin{exercise}{Lagrangian Relaxation for the Assignment Problem with Budget Constraint}\label{ex:lag-ap}
Consider the assignment problem with budget constraint
\begin{align}
 z = \max \quad \sum_{i \in M} \sum_{j \in N} c_{ij} x_{ij} & \\
 \sum_{j \in N} x_{ij} & = 1 & \forall i \in M \label{ex8:con1} \\
 \sum_{i \in M} x_{ij} & = 1 & \forall j \in N \label{ex8:con2} \\
 \sum_{i \in M} \sum_{j \in N} a_{ij} x_{ij} & \le b \label{ex8:con3} \\
 \vc{x} & \in \{0,1\}^{M \times N}
\end{align}
Discuss the strength of different possible Lagrangian relaxations (compared to the optimal LP relaxation value of the original formulation), and the ease or difficulty of solving the Lagrangian subproblems, and the Lagrangian dual. Note that more than one set of constraints can be dualized at the same time!

\begin{solution}
	\input{ex8.tex}
	
\end{solution}

\end{exercise}


\begin{exercise}{Cycle-Elimination Cuts}\label{ex:cec}
  Consider the discussed ILP-formulations for the minimum spanning tree problem. 
  Prove or disprove:
  $$ P_{\rm cec} = P_{\rm sub} $$ 
  
\begin{solution}
	\input{ex9.tex}
	
\end{solution}

\end{exercise}

\begin{exercise}{(Prize Collecting) Steiner Tree Problem}\label{ex:steinertrees}
 Consider the \emph{Steiner tree problem on a graph (STP)} and the \emph{Prize Collecting Steiner tree problem on a graph (PCSTP)} as defined on the lecture slides. Provide ILP formulations for both problems using \emph{directed cutset constraints}. 

\begin{solution}
	\input{ex10.tex}
	
\end{solution}

\end{exercise}

\begin{exercise}{Network Design}\label{ex:nd2}
Given an undirected weighted complete graph $G = (V,E,c)$ with node set $V$ partitioned into $r$ pairwise disjoint clusters $V_1, V_2, ..., V_r$, edge set $E$ and edge cost function $c:E \rightarrow \R^+$, a solution $S = (P,T)$ is defined as $P = \{p_1, p_2, ..., p_r \} \subseteq V$ containing exactly one node from each cluster, i.e., $p_i \in V_i,~ i = 1,...,r$, and $T \subseteq E$ being the edge set of a tree spanning the nodes in $P$. The costs of $S$ are the total edge costs, i.e. $C(T) = \sum_{(u,v) \in T} c(u,v)$, and the objective is to identify a solution with minimum costs.
Formulate this problem as an ILP using an exponential number of \emph{generalized subtour elimination constraints}.

\begin{solution}
	\input{ex11.tex}
	
\end{solution}

\end{exercise}


\end{document}
